package seqlist.singlelinked;

public class SingLeLinkedList {
    private int size;
    private Node head;

    //增
    public void addFirst(int val){
        // 新建一个车厢节点
        Node node=new Node(val);
        // 判断当前的火车是否为空
        if(head==null){
            head=node;
        }else{
            node.next=head;
            head=node;
        }
        size++;
    }

    public void addIndex(int index,int val){
        //1.合法性
        if(index<0||index>size){
            System.out.println("add index illegal!");
            return;
        }
        //头插
        if(index==0){
            addFirst(val);
            return;
        }
        Node node=new Node(val);
        Node prev=head;
        //遍历
        for (int i = 0; i < index-1; i++) {
            prev=prev.next;
        }
        node.next=prev.next;
        prev.next=node;
        size++;
    }

    public void addLast(int val){
        addIndex(size,val);
    }

    //查
    public int getIndexValue(int index){
        if(rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            return node.val;
        }else{
            System.out.println("get index illegal!");
            return -1;
        }
    }

    //改
    public int set(int index,int val){
        if(rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            int oldVal=node.val;
            node.val=val;
            return oldVal;
        }else{
            System.out.println("set index illegal!");
            return -1;
        }
    }

    //删
    //根据索引删除元素
    public void removeIndex(int index){
        if(rangeCheck(index)){
            //删除头节点
            if(index==0){
                Node temp=head;
                head=head.next;
                temp.next=null;
                size--;
            }else {
                Node prev=head;
                for (int i = 0; i < index-1; i++) {
                    prev=prev.next;
                }
                Node cur=prev.next;
                prev.next=cur.next;
                cur.next=null;
                size--;
            }
        }else {
            System.out.println("remove index illegal!");
        }
    }

    public void removeFirst(){
        removeIndex(0);
    }
    public void removeLast(){
        removeIndex(size-1);
    }

    //删除某个元素一次
    public void removeValueOnce(int val){
        if(head!=null&&head.val==val){
            Node temp=head;
            head=head.next;
            temp.next=null;
            size--;
        }else{
            Node prev=head;
            while (prev.next!=null){
                if(prev.val==val){
                    Node cur=prev.next;
                    prev.next=cur.next;
                    cur.next=null;
                    size--;
                    return;
                }
                prev=prev.next;
            }
        }
    }

    //删除链表中所有某个元素
    public void removeValueAll(int val){
        while (head!=null && head.val==val){
            head=head.next;
            size--;
        }
        if(head==null){
            return;
        }else{
            Node prev=head;
            while (prev.next!=null){
                    if(prev.next.val==val){
                        Node cur=prev.next;
                        prev.next=cur.next;
                        cur.next=null;
                        size--;
                    }else{
                        prev=prev.next;
                    }
            }
        }
    }

    //判断元素是否在链表中存在
    public boolean isFind(int val){
        Node temp=head;
        while (temp.next!=null){
            if(temp.val==val){
                return true;
            }
            temp=temp.next;
        }
        return false;
    }


    //判断Index的合法性
    private boolean rangeCheck(int index){
        if(index<0||index>=size){
            return false;
        }
        return true;
    }

    //输出
    public String toString(){
        String ret="";
        Node node=head;
        while(node!=null){
            ret+=node.val;
            ret+="->";
            node=node.next;
        }
        ret+="null";
        return ret;
    }
}

class Node{
    int val;
    Node next;
    public Node(int val){
        this.val=val;
    }
}